package com.lhcai.lc.category.array;

import java.util.Arrays;

/**
 * 238. 除自身以外数组的乘积
 *
 * @author liuhuaicai
 * @since 2024-11-18 20:26
 */
public class Lc238 {
    public static void main(String[] args) {
        Lc238 lc238 = new Lc238();
        System.out.println(lc238.productExceptSelf(new int[]{2, 2, 3, 4,5}));
    }

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        Arrays.fill(answer, 1);
        int left = 0, right = n - 1;
        int lp = 1, rp = 1;
        while (right >= 0 && left < n) {
            answer[right] *= rp;
            answer[left] *= lp;
            lp *= nums[left++];
            rp *= nums[right--];
        }
        return answer;
    }

//    public int[] productExceptSelf(int[] nums) {
//        int n = nums.length;
//        // 前缀积
//        int[] pre = new int[n];
//        pre[0] = nums[0];
//        for (int i = 1; i < n; i++) {
//            pre[i] = pre[i - 1] * nums[i];
//        }
//        // 后缀积
//        int[] suf = new int[n];
//        suf[n - 1] = nums[n - 1];
//        for (int i = n - 2; i >= 0; i--) {
//            suf[i] = suf[i + 1] * nums[i];
//        }
//        // 计算
//        int[] res = new int[n];
//        res[0] = suf[1];
//        res[n - 1] = pre[n - 2];
//        for (int i = 1; i < n - 1; i++) {
//            res[i] = pre[i - 1] * suf[i + 1];
//        }
//        return res;
//    }
}
